// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

// 归并排序函数
// 此函数使用合并排序算法对整数切片进行排序
func mergeSort(slice []int) []int {
	// 基本情况：如果切片有一个元素或为空，则返回切片
	if len(slice) < 2 {
		return slice
	}
	// 将切片分成两半
	mid := (len(slice)) / 2
	// 递归排序两半
	return Merge(mergeSort(slice[:mid]), mergeSort(slice[mid:]))
}

// 此函数将两个排序的整数切片合并为一个排序的切片
func Merge(left, right []int) []int {
	size, i, j := len(left)+len(right), 0, 0
	slice := make([]int, size, size)

	// 比较左右切片的第一个元素，将较小的添加到结果切片
	for k := 0; k < size; k++ {
		if i > len(left)-1 && j <= len(right)-1 {
			slice[k] = right[j]
			j++
		} else if j > len(right)-1 && i <= len(left)-1 {
			slice[k] = left[i]
			i++
		} else if left[i] < right[j] {
			slice[k] = left[i]
			i++
		} else {
			slice[k] = right[j]
			j++
		}
	}
	return slice
}

func main() {
	array := []int{33, 23, 56, 7, 8, 18, 99, 28}
	res := mergeSort(array)
	fmt.Println(res)
}

//$ go run mergeSort.go
//[7 8 18 23 28 33 56 99]
